package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         735,
		Discription: "数组每个位置是个小行星，绝对值代表质量，正代表往右移动，左代表往左移动，碰撞后会留下质量大的，质量一样会一起消失，最后留下哪些小行星",
		Level:       2,
		Labels: map[string]int{
			"正数栈": 1,
			"栈":   1,
		},
	})
}

func AsteroidCollision(asteroids []int) []int {
	s := make([]int, 0)
	for _, val := range asteroids {
		if val == 0 {
			continue
		}

		s = append(s, val)
		//栈顶<0，次栈顶>0才可能发生碰撞
		for len(s) > 1 && s[len(s)-2] > 0 && s[len(s)-1] < 0 {
			//处理正负质量一样一起消失的情况
			if s[len(s)-2]+s[len(s)-1] == 0 {
				s = s[:len(s)-2]
				continue
			}

			//更新碰撞后留下来的小行星
			if s[len(s)-2]+s[len(s)-1] < 0 {
				s[len(s)-2] = s[len(s)-1]
			}
			s = s[:len(s)-1]
		}
	}

	return s
}
